package sword.chapter3String;

/**
 * 最多删除一个字符得到回文
 * 给定一个字符串，请判断如果最多从字符串中删除一个字符能不能得到一个回文字符串。
 * 例如，如果输入字符串"abca"，由于删除字符'b'或者'c'就能得到一个回文字符串，因此输出为true。
 * <p>
 * 要点：
 * 1. 先进行初步回文判断，第一个while循环，截取不是回文的子字符下标start end
 * 2. 再分两种情况截取 start end-1（去尾）或者 start+1 end（掐头），然后判断截取后的子字符串是不是回文字符
 *
 * @author K
 * @date 2021-11-13 17:18
 */
public class S19ValidPalindrome {
    public static void main(String[] args) {
        String s = "abcdbdba";
        boolean result = s19ValidPalindrome(s);
        System.out.println();
    }

    public static boolean s19ValidPalindrome(String s) {
        int start = 0;
        int end = s.length() - 1;
        while (start < s.length() / 2) {
            if (s.charAt(start) != s.charAt(end)) {
                break;
            }
            start++;
            end--;
        }

        return start == s.length() / 2
                || isPalindrome(s, start, end - 1)
                || isPalindrome(s, start + 1, end);
    }

    private static boolean isPalindrome(String s, int start, int end) {
        while (start < end) {
            if (s.charAt(start) != s.charAt(end)) {
                break;
            }
            start++;
            end--;
        }
        return start >= end;
    }


}
